Optimisasi Konveks: Di Luar Konveksitas Dasar: Pelestarian Melalui Supremum Titik-Titik

Meskipun konveksitas dasar mencakup penjumlahan dan penskalaan, pelestarian konveksitas melalui supremum titik-titik adalah operasi dasar untuk membangun fungsi konveks yang tidak trivial dan menetapkan dualitas. Ini menyatakan bahwa bahkan jika kita memiliki keluarga fungsi konveks yang tak terhingga, 'selubung atas' mereka tetap konveks. Jembatan ini memungkinkan kita menganalisis bentuk konveks yang kompleks menggunakan komponen linier sederhana.

1. Definisi Teknis

Untuk sebuah keluarga fungsi $\{f(\cdot, y) \mid y \in \mathcal{A}\}$, supremum titik-titik didefinisikan sebagai:

$$g(x) = \sup_{y \in \mathcal{A}} f(x, y)$$

Domain fungsi ini adalah himpunan titik-titik di mana semua fungsi dalam keluarga terdefinisi dan supremumnya berhingga:

$$\text{dom } g = \{x \mid (x, y) \in \text{dom } f \text{ untuk semua } y \in \mathcal{A}, \sup_{y \in \mathcal{A}} f(x, y) < \infty\}$$

Perspektif Epigraf

Secara geometris, epigraf dari fungsi supremum adalah irisan dari epigraf individu:

$$\text{epi } g = \bigcap_{y \in \mathcal{A}} \text{epi } f(\cdot, y)$$

Karena setiap epigraf individu merupakan himpunan konveks (karena konveksitas $f(x, y)$ terhadap $x$), dan irisan dari sejumlah himpunan konveks apa pun juga konveks, maka konveksitas $g(x)$ dipastikan.

2. Contoh Signifikan

Fungsi Dukungan: $S_C(y) = \sup \{ y^T x \mid x \in C \}$. Fungsi ini selalu konveks, terlepas dari apakah himpunan $C$ konveks atau tidak, karena merupakan supremum dari fungsi linier (afin) terhadap $y$.
Jarak ke Titik Terjauh: $f(x) = \sup_{y \in C} \|x - y\|$. Bahkan untuk himpunan $C$ dengan bentuk tidak teratur, $f(x)$ konveks terhadap $x$ karena norma merupakan fungsi konveks terhadap $x$.
Nilai Eigen Maksimum: Untuk matriks simetris $X$, $f(X) = \lambda_{\max}(X)$ bersifat konveks. Ini berasal dari hasil rasio Rayleigh: $\lambda_{\max}(X) = \sup\{y^T X y \mid \|y\|_2 = 1\}$. Ini merupakan supremum dari fungsi linier terhadap $X$.

Teorema: Representasi Melalui Fungsi Afinitas

Teorema

Hampir semua fungsi konveks dapat dinyatakan sebagai supremum titik-titik dari suatu keluarga fungsi afinitas (pendekatan bawah global).

Intuisi

Pada setiap titik $x_0$, fungsi konveks $f$ memiliki hipervan yang mendukung (fungsi afinitas $h(x) = f(x_0) + g^T(x-x_0)$). Dengan mengambil supremum dari semua hipervan pendukung seperti itu, kita merekonstruksi fungsi $f$ secara tepat.

🎯 Prinsip Utama

Supremum titik-titik melestarikan konveksitas dan infimum titik-titik melestarikan kunkonveksitas. Ini adalah kunci di balik konveksitas norma, fungsi spektral, dan masalah dualitas.

$$g(x) = \sup_{y \in \mathcal{A}} f(x, y) \implies g \text{ adalah konveks jika } f(\cdot, y) \text{ adalah konveks } \forall y$$

PERTANYAAN 1

Jika $f_1(x), f_2(x), \dots, f_n(x)$ adalah fungsi-fungsi konveks, apa yang dapat kita katakan tentang $g(x) = \max\{f_1(x), \dots, f_n(x)\}$?

$g(x)$ selalu konveks.

$g(x)$ konveks hanya jika semua $f_i$ adalah linier.

$g(x)$ konkaf.

$g(x)$ hanya kuasikonveks.

PERTANYAAN 2

Fungsi dukungan $S_C(y) = \sup_{x \in C} y^T x$ bersifat konveks terhadap $y$ meskipun $C$ adalah himpunan non-konveks. Mengapa?

Karena $y^T x$ adalah linier (dan karenanya konveks) terhadap $y$ untuk setiap $x$ yang tetap.

Karena himpunan $C$ secara otomatis dianggap sebagai cangkang konveksnya.

Karena hasil kali dalam selalu merupakan fungsi positif.

Fungsi dukungan hanya konveks jika $C$ dibatasi.

PERTANYAAN 3

Apa hubungan antara epigraf dari $g(x) = \sup f_i(x)$ dengan epigraf individu $\text{epi } f_i$?

$\text{epi } g = \bigcap \text{epi } f_i$

$\text{epi } g = \bigcup \text{epi } f_i$

$\text{epi } g = \text{conv}(\bigcup \text{epi } f_i)$

Tidak ada hubungan langsung.

PERTANYAAN 4

Norm spektral dari suatu matriks $\|X\|_2 = \sigma_{\max}(X)$ bersifat konveks karena...

Ini adalah supremum dari fungsi-fungsi konveks $\|Xv\|_2$ atas vektor satuan $v$.

Jumlah nilai singular selalu konveks.

Semua norma adalah fungsi linier.

Fungsi matriks selalu konveks pada kerucut semi-definit positif.

PERTANYAAN 5

Jika kita mengambil infimum titik-titik dari suatu keluarga fungsi konkaf, apa hasilnya?

Fungsi konkaf.

Fungsi konveks.

Fungsi linier.

Tergantung pada domain.

Tantangan: Dualitas dan Fungsi Konjugat

Analisis Lanjutan MATH008

Dalam analisis konveks, fungsi konjugat $f^*$ didefinisikan melalui supremum titik-titik dari fungsi afinitas: $f^*(y) = \sup_x (y^T x - f(x))$. Transformasi ini sangat penting untuk masalah optimisasi dual.

[Jawaban Singkat] Kondisi orde kedua untuk konveksitas. Buktikan bahwa fungsi $f$ yang dua kali diferensial bersifat konveks jika dan hanya jika domainnya konveks dan $\nabla^2 f(x) \succeq 0$ untuk semua $x \in \mathbf{dom} f.

Solusi: Dengan membatasi $f$ pada garis sembarang $g(t) = f(x + tv)$, konveksitas $f$ setara dengan $g''(t) \geq 0$ untuk semua $v$ dan semua $t$ sehingga $x+tv \in \text{dom } f$. Karena $g'(t) = \nabla f(x + tv)^T v$ dan $g''(t) = v^T \nabla^2 f(x + tv) v$, kondisi $g''(t) \geq 0$ untuk semua $v$ setara dengan matriks Hessian menjadi semidefinit positif: $\nabla^2 f(x) \succeq 0$.

[Jawaban Singkat] Gradien dan Hessian dari fungsi konjugat. Misalkan $\bar{y}$ dan $\bar{x}$ saling terkait melalui $\bar{y} = \nabla f(\bar{x})$, dan $\nabla^2 f(\bar{x}) \succ 0$. (a) Tunjukkan bahwa $\nabla f^*(\bar{y}) = \bar{x}$. (b) Tunjukkan bahwa $\nabla^2 f^*(\bar{y}) = \nabla^2 f(\bar{x})^{-1}. (Output yang Diperlukan: 250 kata)

Jawaban Referensi Pengajar: Untuk bagian (a), kita ingat definisi fungsi konjugat $f^*(y) = \sup_x (y^T x - f(x))$. Untuk $y = \bar{y}$ yang tetap, jika $f$ diferensial dan konveks, supremum dicapai pada titik di mana gradien objektif $h(x) = \bar{y}^T x - f(x)$ menghilang. Menetapkan $\nabla_x (\bar{y}^T x - f(x)) = 0$ menghasilkan $\bar{y} = \nabla f(x)$. Diberikan soal menyatakan $\bar{y} = \nabla f(\bar{x})$, maka jelas bahwa $\bar{x}$ adalah pemaksimal. Berdasarkan sifat konjugat pada titik optimal, kita memiliki $f^*(\bar{y}) = \bar{y}^T \bar{x} - f(\bar{x})$. Diferensiasi kedua sisi terhadap $\bar{y}$ dan menerapkan teorema amplop (atau fakta bahwa $\bar{x}$ adalah pemaksimal), kita peroleh $\nabla f^*(\bar{y}) = \bar{x}$. Ini membenarkan bahwa gradien fungsi konjugat bertindak sebagai pemetaan invers dari gradien fungsi asli.

Untuk bagian (b), kita diferensiasi hubungan $\nabla f^*(\nabla f(x)) = x$ terhadap $x$ menggunakan aturan rantai. Ini memberikan $\nabla^2 f^*(\nabla f(x)) \cdot \nabla^2 f(x) = I$, di mana $I$ adalah matriks identitas. Mengganti $\bar{y} = \nabla f(\bar{x})$, kita peroleh $\nabla^2 f^*(\bar{y}) \cdot \nabla^2 f(\bar{x}) = I$. Karena diberikan $\nabla^2 f(\bar{x}) \succ 0$, Hessian dapat dibalik. Maka, $\nabla^2 f^*(\bar{y}) = [\nabla^2 f(\bar{x})]^{-1}. Hasil elegan ini menunjukkan bahwa kelengkungan lokal fungsi konjugat adalah kebalikan (atau matriks invers) dari kelengkungan fungsi asli pada titik-titik yang bersesuaian. Hubungan ini menjadi pusat analisis metode Newton jenis tertentu dalam ruang dual serta pemahaman transformasi Legendre dalam fisika dan optimisasi.